Polynomial-time approximation schemes for packing and piercing fat objects

We consider two problems: given a collection of n fat objects in a fixed dimension, (1) ( packing) find the maximum subcollection of pairwise disjoint objects, and (2) ( piercing) find the minimum point set that intersects every object. Recently, Erlebach, Jansen, and Seidel gave a polynomial-time approximation scheme (PTAS) for the packing problem, based on a shifted hierarchical subdivision method. Using shifted quadtrees, we describe a similar algorithm for packing but with a smaller time bound. Erlebach et al.'s algorithm requires polynomial space. We describe a different algorithm, based on geometric separators, that requires only linear space. This algorithm can also be applied to piercing, yielding the first PTAS for that problem.     

Construction of best Bregman approximations in reflexive Banach spaces

An iterative method is proposed to construct the Bregman projection of a point onto a countable intersection of closed convex sets in a reflexive Banach space.

     

A fully linear-time approximation algorithm for grammar-based compression

A linear-time approximation algorithm for the grammar-based compression is presented. This is an optimization problem to minimize the size of a context-free grammar deriving a given string. For each string of length n, the algorithm guarantees approximation ratio without suffix tree construction.     

An approximation property of harmonic functions in Lipschitz domains and some of its consequences

An extension of an inequality of J. B. Garnett (1979), with improvements by B. E. J. Dahlberg (1980), on an approximation property of harmonic functions is proved. The weighted inequality proved here was suggested by the work of J. Pipher (1993) and it implies an extension of a result of S. Y. A. Chang, J. Wilson and T. Wolff (1985) and C. Sweezy (1991) on exponential square integrability of the boundary values of solutions to second-order linear differential equations in divergence form. This implies a solution of a problem left open by R. Bañuelos and C. N. Moore (1989) on sharp estimates for the area integral of harmonic functions in Lipschitz domains.

     

Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width

The Multicut problem can be defined as: given a graph G and a collection of pairs of distinct vertices {s_i,t_i} of G, find a minimum set of edges of G whose removal disconnects each s_i from the corresponding t_i. Multicut is known to be NP-hard and Max SNP-hard even when the input graph is restricted to being a tree. The main result of the paper is a polynomial-time approximation scheme (PTAS) for Multicut in unweighted graphs with bounded degree and bounded tree-width. That is, for any ε>0, we present a polynomial-time (1+ε)-approximation algorithm. In the particular case when the input is a bounded-degree tree, we have a linear-time implementation of the algorithm. We also provide some hardness results: we prove that Multicut is still NP-hard for binary trees and that it is Max SNP-hard if we drop any of the three conditions (unweighted, bounded-degree, bounded tree-width). Finally we show that some of these results extend to the vertex version of Multicut and to a directed version of Multicut.     

On the stationary Lp-approximation power to derivatives by radial basis function interpolation

In this paper, we consider approximation to derivatives of a function by using radial basis function interpolation. Most of well-known theories for this problem provide error analysis in terms of the so-called native space, say C_φ. However, if a basis function φ is smooth, the space C_φ is extremely small. Thus, the purpose of this study is to extend this result to functions in the homogenous Sobolev space.     

正系数多项式倒数逼近的点态和整体估计

利用Ditzian-Totik光滑模对于[0,1]上定义的非角连续函数f(x)，且f(x)≠0，文中证明存在正系数多项式Pn(x)及常数C，使得|f9x)-1/Pn(x)|≤Cωψ^λ（f,n^-1/2(ψ(x) 1/√n)^1-λ)。当λ＝1时，上述结果导出已有的整体估计，而当0≤λ＜1时，得到倒数逼近一个新的点态局部估计。     

一般关系下的n-阶FC-粗糙集模型

给出一般模糊环境下n阶-FC-粗糙近似算子的定义,讨论它的一些性质,并通过α-水平集给出各种n-阶模糊粗糙集的表示。进而给出模糊传递闭包近似算子的定义,得到相应的结果。     

D.C.隶属函数模糊集及其应用(Ⅱ)--D.C.隶属函数模糊集的万能逼近性

本文是D．C．隶属函数模糊集及其应用系列研究的第二部分。指出在实际问题中普遍选用的三角形、半三角形、梯形、半梯形、高斯型、柯西型、S形、Z形、π形隶属函数模糊集等均为D．C．隶属函数模糊集，建立了D．C．隶属函数模糊集对模糊集的万有逼近性。探讨了D．C．隶属函数模糊集与模糊数之间的关系，给出了用D．C．隶属函数模糊集逼近模糊数的e-Cellina逼近形式，得到模糊数与D．C．函数之间的一个对应算子，指出了用模糊数表示D．C．函数的问题。     

Algorithms for flows with parametric capacities

We consider the problem of finding maximal flows with respect to capacities which are linear functions of a parametert [0,T]. Since this problem is a special case of a parametric linear program the classichorizontal approach can be applied in which optimal solutions are computed for successive subintervals of [0,T]. We discuss an alternative algorithm which approximates in each iteration the optimal solution for allt [0,T]. Thisvertical algorithm is a labeling type algorithm where the flow variables are piecewise linear functions. Flow augmentations are done alongconditional flow augmenting paths which can be found by modified path algorithms. The vertical algorithm can be used to solve the parametric flow problem optimally as well as to compute a good approximation for allt if the computation of the optimal solution turns out to be too time consuming.Partially supported by NSF Grants ECS-8412926 and INT-8521433, and NATO Grant RG 85/0240.